package cn.djb.day23;

/**
 * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution_2 {
    public int[] constructArr(int[] a) {
        int length = a.length;
        int[] res = new int[length];
        if (length == 0) return res;
        res[0] = 1;
        for (int i = 1; i < length; i++) {
            res[i] = a[i-1] * res[i - 1];
        }

        int tmp = 1;
        for (int i = length - 2; i >= 0; i--) {
            tmp *= a[i+1];
            res[i] *= tmp;
        }
        return res;
    }
}